/**
 * 今天，书店老板有一家店打算试营业customers.length分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
 * <p>
 * 在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
 * 书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续X 分钟不生气，但却只能使用一次。
 * 请你返回这一天营业下来，最多有多少客户能够感到满意。
 * <p>
 * 示例：
 * 输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
 * 输出：16
 * 解释：
 * 书店老板在最后 3 分钟保持冷静。
 * 感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
 * <p>
 * 提示：
 * 1 <= X <=customers.length ==grumpy.length <= 20000
 * 0 <=customers[i] <= 1000
 * 0 <=grumpy[i] <= 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/grumpy-bookstore-owner
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q01052m {

    /**
     * 滑动窗口+前缀和、后缀和，效率比较低
     *
     * @param customers
     * @param grumpy
     * @param minutes
     * @return
     */
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int[][] temp = new int[customers.length + 2][3];
        for (int i = 1; i < temp.length - 1; i++) {
            temp[i][1] = temp[i - 1][1];
            if (grumpy[i - 1] == 0) {
                temp[i][1] += customers[i - 1]; // 可以生气情况下的前缀和
            }
            temp[temp.length - 1 - i][2] = temp[temp.length - i][2];
            if (grumpy[temp.length - 2 - i] == 0) {
                temp[temp.length - 1 - i][2] += customers[temp.length - 2 - i]; // 可以生气情况下的后缀和
            }
            temp[i][0] += temp[i - 1][0] + customers[i - 1]; // 前缀和
        }
        int ans = 0;
        for (int i = 1; i <= temp.length - 1 - minutes; i++) {
            ans = Math.max(ans, temp[i - 1][1] + temp[i + minutes][2] + (temp[i + minutes - 1][0] - temp[i - 1][0])); // 滑动窗口
        }
        return ans;
    }
}
